Personal verification using a handwritten signature forms a signature verification culture centering around the West. On the other hand, the digital information society requires building a similar verification system. To meet such requirements, for example, Japanese Patent Laid-Open Nos. 10-171926, 10-40388, and 5-324805 have proposed signature verification systems. The signature verification systems described in these references will be described below.
The technique described in the references will be described with reference to FIG. 14. A person signs on an input device 3021 such as a digitizer or the like using a digital pen 3022. As for the input signature, the position coordinates (xin, yin) and handwriting pressure pin of the digital pen are read at unit time intervals, they are converted into an electrical signal as time-series data, and the electrical signal is sent to a data controller 3023. The data controller 3023 compares the input data with a standard pattern serving as an evaluation reference to check if the input signature is an original one.
As a method of detecting the difference between the standard pattern and input pattern, a fuzzy scheme (Japanese Patent Laid-Open No. 5-324805) and a dynamic programming method (Japanese Patent Laid-Open Nos. 10-171926 and 10-40388) are used in the above proposals.
The dynamic programming method is described in T. Y. Yong & K-S. Fu, co-editors, “Handbook of Pattern Recognition and Image Processing”, Academic Press, 1986.
Both these methods require pattern matching between time-series data of x- and y-coordinate values as discretized Cartesian coordinates obtained by the signature, and time-series data of standard x- and y-coordinate values, and weighting associated with the handwriting pressure or the velocity of time-series data.
On the other hand, a curve that allows a finite number of intersections, as shown in FIG. 15, is called a curve immersed in a two-dimensional plane in mathematics. Signature data can be recognized as a curve immersed in a two-dimensional plane.
Since signature characters run on or are simplified extremely, it is advisable to consider them as a symbol or geometric curve rather than characters. In practice, since personal authentication has been implemented so far based on such extremely modified characters, a recognition method of handwritten characters as normal characters is limited. Therefore, the present application recognizes signature characters based on classification of curves, i.e., the signature verification program is replaced by the problem of similarity or congruence of curve figures. For this reason, a curve obtained from the signature will be referred to as a signature curve hereinafter.
From such point of view, the conventional signature verification technique that uses discretized Cartesian coordinates suffers the same problem as in a classification method of curves using x- and y-coordinates, as will be described below, and such problem hinders verification.
As the inventions of a method of classifying curve shapes, a series of figure shape learning/recognition methods of Japanese Patent Laid-Open Nos. 5-197812, 6-309465, and 7-37095 are known. The inventions described in these Laid-Open publications will be described below as the prior art.
Assume that a dot sequence is given by {d[i]|i=1, . . . , N}. Note that d[i] is a two-dimensional vector quantity of an integer value, and the dot sequence is a two-dimensional lattice coordinate sequence of d[i]=(x[i], y[i]). For the sake of simplicity, assume that the dot sequence is closed, and number i is that of modulo N. Hence, d[i modulo N]. Also, the dot sequence has an order along connectivity of a curve, and none of a hair stroke (FIG. 16A), a bent curve more than a resolution (FIG. 16B), double lines (FIG. 16C), and an intersection (FIG. 16D) are present as a thin-line-converted curve for the sake of simplicity. Note that an actual signature curve is numbered time-serially, and traces indicated by blank curves can be reproduced within the range of the dot resolution, thus posing no problem. However, in this case, the aforementioned assumptions were set for the sake of simplicity.
A “curvature” in Japanese Patent Laid-Open Nos. 5-197812, 6-309465, and 7-37095 will be defined. As is professed in Japanese Patent Laid-Open No. 6-309465, a “curvature” that the inventor of this application called is not a curvature in the mathematical sense. In practice, this definition does not give correct information since it conflicts with the argument of congruence of figures, as will be explained later. Hence, in this specification, the curvature defined in the above references will be referred to as a pseudo curvature.
FIGS. 17A to 17C are views for explaining the definition of the pseudo curvature in the prior art. A pair of dots (d[i−k], d[i+k]) (two-dimensional vector) will be examined for pixel d[i]. A perpendicular is dropped from d[i] to a line segment defined by (d[i−k], d[i+k]), and its height is represented by B[k]. Also, the length of the line segment defined by (d[i−k], d[i+k]) is represented by L[i,k]. k assumes natural numbers 1, 2, 3, . . . in turn, and B[k] is calculated for each k. For given parameter E, maximum k is obtained within the range B[k]<E.
At this time, two different pseudo curvatures are defined as follows in accordance with FIGS. 17A to 17C.
1. First pseudo curvature (Japanese Patent Laid-Open No. 5-197812): Angle θ[i] vector (d[i+k], d[i]) makes with vector (d[i−k], d[i]) is defined as the first pseudo curvature. {(i, θ[i], |i=1, . . . , N} as the distribution function of each pixel number i is called a first pseudo curvature function.
2. Second pseudo curvature (Japanese Patent Laid-Open Nos. 6-309465 and 7-17095): A circle defined by three points (d[i+k], d[i], d[i−k]) on a curve is determined, and if R[i] represents the radius of that circle, 1/R[i] is defined as the second pseudo curvature. {(i, 1/R[i]) |i=1, . . . , N} as the distribution function of each pixel number i is called a second pseudo curvature function.
The two pseudo curvatures defined as described above are not invariant with respect to affine (congruence) transformation even by approximation, and a limit is often not present even at a limit at which zero pixel resolution is set. That is, these pseudo curvatures are not mathematically well-defined. For this reason, any obtained figures are not invariant with respect to affine transformation even by approximation or the like and are indeterminate values. Japanese Patent Laid-Open Nos. 5-197812, 6-309465, and 7-37095 compensate for such mathematical drawbacks using a neural net.
An algorithm will be explained with reference to FIG. 18. In step SS1, a memory or the like is initialized. For example, a curve figure is converted into thin-line data to remove patterns shown in FIGS. 16A to 16D. In step SS2, the first or second pseudo curvatures of the curve are computed to calculate a pseudo curvature distribution. In step SS3, the obtained pseudo curvature distribution is processed using a neural net to classify the curve.
As will be described later, the aforementioned pseudo curvature is mathematically unstable and, hence, a learnable process such as the neural net or the like must be done as in step SS3. This is an important fact. According to the present invention to be described later, since no such mathematical drawbacks are present, the curve figure can be classified using a classic logical circuit.
As is known, classification of a curve immersed in a two-dimensional plane can be defined by a Frenet-Serret's formula. (For example, refer to L. P. Eisenhart, “A Treatise on the Differential Geometry of Curves and Surfaces”, Ginn and Company 1909.) Let φ be the adjacent angle with respect to a curve, and s be the length of the curve (arc length) determined by a natural measure on the two-dimensional plane, as shown in FIG. 19. Then, the following formula can be defined:
                                          (                                                                                                      ⅆ                                                                                                                                  ⅆ                      s                                                                                        k                                                                                                  -                    k                                                                                                              ⅆ                                                                                                                                  ⅆ                      s                                                                                            )                    ⁢                      (                                                                                cos                    ⁡                                          (                                              ϕ                        ⁡                                                  (                          s                          )                                                                    )                                                                                                                                        sin                    ⁡                                          (                                              ϕ                        ⁡                                                  (                          s                          )                                                                    )                                                                                            )                          =        0                            (        1        )            
Note that k=dφ/ds is a curvature, and 1/k is a so-called radius of curvature. This formula is called the Frenet-Serret's formula, and classic differential geometry teaches that the local natures of a curve are perfectly determined by this formula.
Note that the curvature k in the theory of curves in classic differential geometry is an extrinsic curvature, and is a kind of connection according to the terminology of modern differential geometry. The curvature k is defined on one dimension, and does not have any direct relation with an intrinsic curvature called a curvature tensor which does not assume any value on two or more dimensions. Note that the terminology of modern differential geometry is described in, e.g., M. Nakahara, “Geometry, Topology and Physics”, Institute of Physics 1990. Also, the intrinsic and extrinsic curvatures are related by “Gauss' surprise theorem” in case of a two-dimensional surface.
Upon adopting notation which is independent of coordinates, a curvature in classic differential geometry is κ=kds. This is a differential form of order one, or one-form, in the terminology of modern differential geometry.
As is well known, the relationship between one form (distribution function) and function (scalar function) is determined by transformability with respect to coordinate transformation. That is, upon coordinate transformation of the arc length s into an infinitely-differentiable function g(s) that monotonously increases with s, the (scalar) function is f(s)=f(g(s)). On the other hand, one-form (or distribution function) is transformed into f(s)ds=f(g(s))(ds/dg)dg. Note that (ds/dg) means the Jacobian.
Therefore, the curvature is a distribution function that must consider the Jacobian with respect to coordinate transformation, and upon coordinate transformation of the arc length s into the function g(s) that monotonously increases with s, a curvature k(s) must be transformed into (k(g(s))(ds/dg) to obtain a mathematically significant result.
However, the pseudo curvatures defined in Japanese Patent Laid-Open Nos. 5-197812, 6-309465, and 7-37095 do not consider the Jacobian in coordinate transformation from the arc length into the number of pixels. In practice, transformation from a line segment into two-dimensional image data is arbitrary, and the number of dots that express an identical line segment is not constant with respect to the length of the line segment, as shown in FIGS. 20A and 20B. That is, the number of dots can be considered as a function of the arc length, and when a distribution function like a curvature in classic differential geometry is expressed by the number of dots, that expression itself must be considered as coordinate transformation from the arc length. Especially, two-dimensional image data does not normally have any degree of freedom in rotation, and no degrees of freedom in translation less than the pixel size are present. That is, the number of dots along the arc is a function which changes with respect to the arc length s as coordinates along the arc, and when the curvature as one form (distribution function) is expressed, it is important to give information which indicates a coordinate system of integer values discretized by the Jacobian.
However, the pseudo curvatures described in the prior art do not take such consideration.
Affine transformation will be explained below. In the field of mathematics, congruence transformation has been studied in the field of affine geometry, and a congruence condition between figures defined on a two-dimensional plane purely means that two figures perfectly overlap each other after appropriate equivalent affine transformation (translation and rotation). Similarity includes enlargement/reduction transformation in this equivalent affine transformation. Such transformation is called affine transformation.
Therefore, as can be understood from the above description, signature verification is equivalent to similarity or congruence of curve figures in a pure sense. However, even for an identical person, signature curves obtained have different various conditions such as enlargement/reduction, translation, angular deviation, and the like upon every signature. Of these signature curves, a shape invariant to the aforementioned affine transformation is present, and a signature fluctuates naturally.
For this reason, it is important that the processing algorithm has no conflict with affine transformation so as to minimize verification process errors upon verification.
However, the conventional signature handwriting analysis method and apparatus (Japanese Patent Laid-Open Nos. 10-171926, 10-40388, and 5-324805) are not invariant with respect to such affine transformation, as will be described below, since pattern matching using discretized Cartesian coordinates is done, thus posing various problems.
Furthermore, it is very difficult to match two curve figures upon excluding the degree of freedom in affine transformation when a figure described as an actually drawn curve is involved. A “line” on the digitizer has a width, and is not mathematically a strict line. That is, the input device 3021 such as the digitizer or the like in FIG. 14 has a resolution determined by hardware, and when a curve figure is expressed as two-dimensional image data, as shown in FIGS. 20A and 20B, the figure strongly depends on its expression method due to quantization errors.
However, this dependence is very small since a curve figure seems to express a strict figure for the human eye when the curve figure is sufficiently larger than the pixel size of image data. Under such illusion, we normally handle image data.
But if such sense of understanding is directly applied to mathematical quantities (e.g., the pseudo curvatures, and information of lattice data determined by Cartesian coordinates upon evaluating similarity in this case), and definition is made without any mathematical strictness, we lose logic and rationality.
In order to define a difference/similarity between given objects A and B in mathematics, topology must be introduced. In the current problems, comparison must be made by introducing a kind of topology. At this time, topology must be weak enough to solve the problem that the actual “line” has a width, and problems of quantization errors, discretization errors, and the like such as curvatures, and the like. If identity (congruence) of figures is to be discriminated finally, an algorithm must be invariant or approximately invariant with respect to affine transformation.
The pseudo curvatures in the prior art and the conventional signature verification method that processes using x- and y-coordinate sequences do not meet such requirements. For example, as can be immediately understood from FIGS. 21A and 21B, the pseudo curvatures formed in the prior art are not invariant with respect to affine transformation and, especially, rotation.
As shown in FIG. 21A, when straight lines which form a line figure agree with the pixel lattices, the number of dots and arc length are linked via linear transformation having a magnification-multiple correspondence. However, when straight lines are oblique, as shown in FIG. 21B, pixels which express these lines form jaggies, and the ratio of the number of pixels required for expression and length is not constant. In practice, in order to express a straight line of approximately √2 (pixels) having an angle of 45°, as shown in FIG. 21B, three pixels are required, and the number of pixels becomes about twice larger than the length. As shown in FIGS. 20A and 20B, a smallest angular difference often abruptly changes the number of pixels required to express a line segment.
By reflecting this fact, the graph of pseudo curvature distribution functions (either the first or second pseudo curvatures) in FIGS. 21A and 21B is as shown in FIG. 22. In FIG. 22, the abscissa plots the number of pixels, and the ordinate plots the pseudo curvature. The bold curve indicates a case wherein the straight lines agree with the pixel direction, as shown in FIG. 21A, and the thin curve indicates a case herein the straight line is oblique, as shown in FIG. 21B. The appearance of the pseudo curvature function largely changes with respect to transformation, i.e., rotation.
Conversely, by changing the direction of rotation or the like with respect to a graph that plots the same number of pixels and pseudo curvatures, different figures are recognized as identical figures.
To correct such contradictions, the prior art (Japanese Patent Laid-Open Nos. 10-171926, 10-40388, and 5-324905) adopts a correction method using a neural net. However, it is generally difficult to reproduce mathematically rational information from information which is not mathematically well-defined.
In Japanese Patent Laid-Open Nos. 5-324805, 10-171926, and 10-40388, correction based on a fuzzy scheme or dynamic programming scheme is done. However, these errors include correction components resulting from information which is not mathematically well-defined, thus impairing the reliability of signature verification.